package com.itheima.d5_algorithm;

import java.util.Scanner;

//目标：了解二分查找的规则和实现方式
public class Demo03 {
    public static void main(String[] args) {
        //注意：二分查找的数组必须是有序的！
        int[] arr = {11, 22, 33, 44, 55, 66};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入要查询的数据：");
        int key = sc.nextInt();

        //需求：利用二分查找实现，从数组arr中查询key的索引
        int index = getIndex(arr, key);
        System.out.println(key + "在数组中的索引位置是：" + index);
    }

    /**
     * 1.定义方法，利用二分查找，查找制定数组中制定数据所在的索引，没有找到返回-1
     * 明确参数：int[] arr, int key
     * 明确返回值：int
     */
    public static int getIndex(int[] arr, int key) {
        //2.定义两个变量，分别代表左边和右边的索引位置
        int left = 0;
        int right = arr.length - 1;

        //3.二分查找的过程是不断重复的，当left<=right的就需要重复找
        while (left <= right) {
            //4.找中间索引
            int mid = (left + right) / 2;

            //5.拿出mid索引位置的数据，和要查询的key数据比较大小
            if (arr[mid] > key) {
                //条件成立，数据是升序排序的，mid位置数据大了，那说明mid右边更大！right需要改变，变成mid-1
                right = mid - 1;
            } else if (arr[mid] < key) {
                //条件成立，说明mid位置数据更小，左边就要排除，left = mid + 1
                left = mid + 1;
            } else {
                //找到了，key在数组arr的索引是mid
                return mid;
            }
        }

        //6.如果代码执行到这，方法还未结束，说明没有找到
        return -1;
    }
}
